/*
    最大公约数、同余原理
    
    前置知识 : 无

    求最大公约数
    1) 欧几里得算法的过程 : 辗转相除法
    2) 正确性的证明过程见代码注释部分，我润色的证明过程非常好懂，不过直接记忆过程即可
    3) 求gcd(a,b)，其中a>b，时间复杂度为O((log a)的3次方)，时间复杂度证明略，这个复杂度足够好了
    4) 简单转化就可以求最小公倍数
    5) 更高效求最大公约数的Stein算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣可以继续研究
    6) 不比赛的同学，哪怕你的目标是最顶级的公司应聘、还是考研，掌握这个只有一行的函数已经足够！

    gcd(a, b) { return b == 0 ? a : gcd(b, a % b); }

    同余原理
    1) 介绍背景
    2) 加法、乘法每一步计算完后直接取模，减法则为(a-b+m)%m
    3) 要确保过程中不溢出，所以往往乘法运算的用long类型做中间变量
    4) 除法的同余需要求逆元，会在【扩展】课程里讲述，较难的题目才会涉及 

    ================================================

    求最大公约数相关的经典题目
    一个正整数如果能被 a 或 b 整除，那么它是神奇的。
    给定三个整数 n , a , b ，返回第 n 个神奇的数字。
    因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
    注意：
    本题用到“二分答案法”和“容斥原理”两个重要的算法，不过用的非常浅，之前没有接触过也能理解
    “二分答案法”非常巧妙可以解决很多问题，整套内容会在后续的【必备】课程里做成专题视频讲述
    “容斥原理”可以考的非常难，也会在后续的【扩展】课程里做成专题视频讲述

    同余原理的测试
    代码中用对数器进行了验证
    你也可以设计实验用对数器随意验证

*/